"""
题目：https://leetcode-cn.com/problems/sort-list/
    给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
    输入：head = [4,2,1,3]
    输出：[1,2,3,4]

思路：自顶向下归并排序方法。总体思想是使用归并排序，首先获取链表的中间节点，然后分别排序中间节点的左、右两边的链表，最后将排序好的链表按照顺序合并即可。
时间复杂度：O(nlogn)
空间复杂度：O(logn)
"""
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        mid = self.get_mid(head)
        l = head
        r = mid.next
        mid.next = None
        return self.merge(self.sortList(l),self.sortList(r))

    def get_mid(self,head):
        slow,fast = head,head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        return slow
        
    def merge(self,l,r):
        dummy = ListNode(-1)
        head = dummy
        while l and r:
            if l.val < r.val:
                head.next = l
                l = l.next
            else:
                head.next = r
                r = r.next
            head = head.next
        if l:
            head.next = l
        if r:
            head.next = r
        return dummy.next
